package com.fyl.leetcode.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author:fyl
 * @date 2021/5/20 19:57
 * @Modified By:
 * @Modified Date:
 * @Description: 93
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址
 *
 * 1、维护一个数组(res[i],长度为4)保存递归时的结果，并设置一个resIndex记录下一结果的位置。
 * 2、将字符串s，分解成char数组(ch[i])，并设置一个index记录一下元素的位置。
 * 3、如果 resIndex == 4 && index == ch.length 说明已经成功生成一个IP地址，将其加入list中即可。
 * 4、如果 resIndex < 4 && index == ch.length || resIndex == 4 && index < ch.length 说明此次递归生成的res不能组成有效的IP地址，return。
 * 5、如果当前元素 ch[index] 是否为0，当前元素都可以进行下次递归。
 * 6、如果当前元素 ch[index] == 0 ，又因为前导元素不能是0，所以0只能单独存在，不在递归后续 ch[index + 1] 和 ch[index + 2]。
 * 7、如果当前元素 ch[index] != 0 ，只需要判断 ch[index] * 10 + ch[index] 和 ch[index] * 100 + ch[index + 1] * 10 + ch[index + 2]
 * 所组成的元素是否满足 大于0 && 小于256 即可
 */
public class RestoreIpAddresses {
    ArrayList<String> list = null;

    public List<String> restoreIpAddresses(String s) {
        list = new ArrayList<String>();
        creatString(s.toCharArray(), 0, new int[4], 0);
        return list;
    }

    public void creatString(char[] ch, int index, int[] res, int resIndex) {
        if (resIndex == 4 && index == ch.length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                sb.append(res[i]);
                sb.append(".");
            }
            sb.append(res[3]);
            list.add(sb.toString());
            return;
        }
        if (resIndex < 4 && index == ch.length || resIndex == 4 && index < ch.length) {
            return;
        }
        int temp = ch[index] - '0';
        res[resIndex] = temp;
        creatString(ch, index + 1, res, resIndex + 1);
        if (temp != 0) {
            for (int i = 1; i < 3 && index + i < ch.length; i++) {
                temp = temp * 10 + (ch[index + i] - '0');
                if (temp < 256 && temp > 0) {
                    res[resIndex] = temp;
                    creatString(ch, index + i + 1, res, resIndex + 1);
                } else {
                    break;
                }
            }
        }
    }
}
